package com.sakura.动态规划;

import java.util.Arrays;

public class Code983_最低票价 {

    //                           0  1   2
    private static int[] plan = {1, 7, 30};

    // 递归暴力
    public int mincostTickets1(int[] days, int[] costs) {
        return f1(days, costs, 0);
    }

    private int f1(int[] days, int[] costs, int i) {
        if (i == days.length) {
            return 0;
        }
        int ans = -1;
        for (int k = 0, j = i; k < 3; k++) {
            // days[i] + plan[k] > days[j] 如果选择方案的天数 + day[i] > day[j],表示方案还可以继续使用
            while (j < days.length && days[i] + plan[k] > days[j]) {
                j++;
            }
            if (ans == -1) {
                ans = f1(days, costs, j);
            } else {
                ans = Math.min(ans, costs[k] + f1(days, costs, j));
            }
        }
        return ans;
    }

    private int[] dp;

    // 记忆化搜索
    public int mincostTickets2(int[] days, int[] costs) {
        dp = new int[days.length];
        Arrays.fill(dp, Integer.MAX_VALUE);
        return f2(days, costs, 0, dp);
    }

    private int f2(int[] days, int[] costs, int i, int[] dp) {
        if (i == days.length) {
            return 0;
        }
        if (dp[i] != Integer.MAX_VALUE) {
            return dp[i];
        }
        int ans = Integer.MAX_VALUE;
        for (int k = 0, j = i; k < 3; k++) {
            while (j < days.length && days[i] + plan[k] > days[j]) {
                j++;
            }

            ans = Math.min(ans, costs[k] + f2(days, costs, j, dp));
        }
        dp[i] = ans;
        return ans;
    }

    private static int MAX_LENGTH = 366;
    private static int[] dp2 = new int[MAX_LENGTH];

    // 自底向上：从依赖最底部的状态，往前推，依次推到最顶部的状态
    // n - 1 的票价依赖 n
    // n - 2 的票价依赖 n - 1
    public int mincostTickets3(int[] days, int[] costs) {
        int n = days.length;
        Arrays.fill(dp2, 0, n + 1, Integer.MAX_VALUE);
        dp2[n] = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int k = 0, j = i; k < 3; k++) {
                while (j < days.length && days[i] + plan[k] > days[j]) {
                    j++;
                }
                dp[i] = Math.min(dp[i], costs[k] + dp[j]);
            }
        }
        return dp[0];
    }
}
